冯志伟 | 自然语言的计算复杂性研究

理论语言学五道口站 2022-08-12

编者按

《理论语言学五道口站》（2022年第20期，总第223期）转载分享一篇冯志伟教授的论文，标题为《自然语言的计算复杂性研究》，该文为许国璋先生纪念特刊专稿。文中，冯志伟教授尝试回答了许国璋先生提出的自然语言的计算复杂性究竟有多大的问题，讨论了正则语法、上下文无关语法的计算复杂性，说明了交叉系列依存结构的计算复杂性，表达了对许国璋先生的缅怀之情。

本次分享已由冯志伟教授授权转载。

人物简介

冯志伟

冯志伟，1939年生，计算语言学家，昆明一中中学毕业，北京大学和中国科技大学研究生院两次研究生毕业，文革期间首次测出汉字熵为9.65比特，为汉字多八位编码提供了语言学支持。法国留学时师从国际计算语言学学会第一任主席Vauquois，研制了世界上第一个把汉语译为多种外语的机器翻译系统，是第一个出席国际计算语言学顶会COLING的中国学者。长期从事语言学和计算机科学的跨学科研究，曾在德国、韩国的大学担任教授，讲授自然语言处理课程，出版论著30多部，发表论文400多篇，主持研制国际标准1项、国家标准1项、国家规范3项，参与研制国家标准13项。担任国内外著名杂志编委，曾任中国语文现代化学会副会长，中国人工智能学会理事，《中文信息学报》顾问。工作单位：教育部语言文字应用研究所。2006年获奥地利维斯特奖，2018年获中国计算机学会NLPCC 杰出贡献奖，2021年获中国中文信息学会会士称号，2022年获香港圣弗朗西斯科技人文奖。